﻿#pragma once
#include "base.h"
#include "mymath.h"

class CStrToIndex
{
public:
	CStrToIndex() {

	}
	CStrToIndex(const vector<string>& wordList) {
		for (const auto& str : wordList)
		{
			Add(str);
		}
	}
	int Add(const string& str)
	{
		if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
		m_mIndexs[str] = m_strs.size();
		m_strs.push_back(str);
		return  m_strs.size()-1;
	}
	vector<string> m_strs;
	int GetIndex(const string& str)
	{
		if (m_mIndexs.count(str)) { return m_mIndexs[str]; }
		return -1;
	}
protected:
	unordered_map<string, int> m_mIndexs;
};

class CWords
{
public:
	void Add(const string& word)
	{
		m_strStrs.insert(word);
	}
	bool Search(const string& word)
	{
		return Search(m_strStrs.begin(), m_strStrs.end(), 0, word.length(), word);
	}
protected:
	bool Search(std::set<string>::const_iterator begin, std::set<string>::const_iterator end, int iStrBegin, int iStrEnd, const string& str)
	{
		int i = iStrBegin;
		for (; (i < iStrEnd) && (str[i] != '.'); i++);
		auto it = std::equal_range(begin, end, str, [&iStrBegin, &i](const string& s, const string& sFind)
			{
				return s.substr(iStrBegin, i - iStrBegin) < sFind.substr(iStrBegin, i - iStrBegin);
			});
		if (i == iStrBegin)
		{
			it.first = begin;
			it.second = end;
		}
		if (it.first == it.second)
		{
			return false;
		}
		if (i == iStrEnd)
		{
			return true;
		}
		if (i + 1 == iStrEnd)
		{
			return true;
		}
		string tmp = str;
		for (char ch = 'a'; ch <= 'z'; ch++)
		{
			tmp[i] = ch;
			auto ij = std::equal_range(it.first, it.second, tmp, [&ch, &i](const string& s, const string& sFind)
				{
					return s[i] < sFind[i];
				});
			if (ij.first == ij.second)
			{
				continue;
			}

			if (Search(ij.first, ij.second, i + 1, iStrEnd, str))
			{
				return true;
			}
		}
		return false;
	}

	std::set<string> m_strStrs;
};
class WordDictionary {
public:
	WordDictionary() {
		for (int i = 0; i < 26; i++)
		{
			m_str[i] = std::make_unique<CWords>();
		}
	}

	void addWord(string word) {
		m_str[word.length()]->Add(word);
	}

	bool search(string word) {
		return m_str[word.length()]->Search(word);
	}
	std::unique_ptr<CWords> m_str[26];
};

//iCodeNum 必须大于等于可能的字符数
template<int MOD = 1000000007>
class CHashStr {
public:
	CHashStr(string s, int iCodeNum, int iCodeBegin = 1, char chBegin = 'a') {
		m_c = s.length();
		m_vP.resize(m_c + 1);
		m_vP[0] = 1;
		m_vHash.resize(m_c + 1);
		for (int i = 0; i < m_c; i++)
		{
			const int P = iCodeBegin + iCodeNum;
			m_vHash[i + 1] = m_vHash[i] * P + s[i] - chBegin + iCodeBegin;
			m_vP[i + 1] = m_vP[i] * P;
		}
	}
	//iMinValue将被编码为0,iMaxValue被编码为iMaxValue-iMinValue。
	CHashStr(const int* data, int len, int iMinValue = 0, int iMaxValue = 9) {
		m_c = len;
		m_vP.resize(m_c + 1);
		m_vP[0] = 1;
		m_vHash.resize(m_c + 1);
		const int P = iMaxValue - iMinValue + 1;
		for (int i = 0; i < m_c; i++)
		{
			const int iCurCode = data[i] - iMinValue;
			assert((iCurCode >= 0) && (iCurCode < P));
			m_vHash[i + 1] = m_vHash[i] * P + iCurCode;
			m_vP[i + 1] = m_vP[i] * P;
		}
	}
	//包括left right
	int GetHash(int left, int right)
	{
		return (m_vHash[right + 1] - m_vHash[left] * m_vP[right - left + 1]).ToInt();
	}
	inline int GetHash(int right)
	{
		return m_vHash[right + 1].ToInt();
	}
	int GetHashExincludeRight(int left, int right)
	{
		return (m_vHash[right] - m_vHash[left] * m_vP[right - left]).ToInt();
	}
	inline int GetHashExincludeRight(int right)
	{
		return m_vHash[right].ToInt();
	}
	int m_c;
	vector<C1097Int<MOD>> m_vP;
	vector<C1097Int<MOD>> m_vHash;
};

template<int MOD2 = 1000000009>
class C2HashStr
{
public:
	C2HashStr(string s) {
		m_pHash1 = std::make_unique<CHashStr<>>(s, 26);
		m_pHash2 = std::make_unique < CHashStr<MOD2>>(s, 27, 0);
	}
	C2HashStr(const int* data, int len, int iMinValue = 0, int iMaxValue = 9)
	{
		m_pHash1 = std::make_unique<CHashStr<>>(data, len, iMinValue, iMaxValue);
		m_pHash2 = std::make_unique < CHashStr<MOD2>>(data, len, iMinValue, iMaxValue);
	}
	//包括left right
	long long GetHash(int left, int right)
	{
		return (long long)m_pHash1->GetHash(left, right) * (MOD2 + 1) + m_pHash2->GetHash(left, right);
	}
	long long GetHash(int right)
	{
		return (long long)m_pHash1->GetHash(right) * (MOD2 + 1) + m_pHash2->GetHash(right);
	}
	//包括Left，不包括Right
	long long GetHashExincludeRight(int left, int right)
	{
		return (long long)m_pHash1->GetHashExincludeRight(left, right) * (MOD2 + 1) + m_pHash2->GetHashExincludeRight(left, right);
	}
	long long GetHashExincludeRight(int right)
	{
		return (long long)m_pHash1->GetHashExincludeRight(right) * (MOD2 + 1) + m_pHash2->GetHashExincludeRight(right);
	}
private:
	std::unique_ptr<CHashStr<>> m_pHash1;
	std::unique_ptr<CHashStr<MOD2>> m_pHash2;
};


template<int MOD = 1000000007>
class CDynaHashStr {
public:
	CDynaHashStr(int iCodeNum, int iCodeBegin = 1, char chBegin = 'a') :m_iUnit(iCodeNum + iCodeBegin), m_iP(1), m_iBegin(iCodeBegin - chBegin)
	{

	}
	inline void push_back(const char& ch)
	{
		const int iNum = ch + m_iBegin;
		m_iHash *= m_iUnit;
		m_iHash += iNum;
		m_iP *= m_iUnit;
	}
	inline void push_front(const char& ch)
	{
		const int iNum = ch + m_iBegin;
		m_iHash += m_iP * iNum;
		m_iP *= m_iUnit;
	}
	inline int GetHash() const
	{
		return m_iHash;
	}
	const int m_iUnit;
	const int m_iBegin;
	C1097Int<MOD> m_iHash;
	C1097Int<MOD> m_iP;
};

template<int MOD2 = 1000000009>
class C2DynaHashStr {
public:
	C2DynaHashStr(int iCodeNum, int iCodeBegin = 1, char chBegin = 'a')
	{
		m_pHash1 = new CDynaHashStr<>(iCodeNum, iCodeBegin, chBegin);
		m_pHash2 = new CDynaHashStr<MOD2>(iCodeNum, iCodeBegin, chBegin);
	}
	~C2DynaHashStr()
	{
		delete m_pHash1;
		delete m_pHash2;
	}
	inline void push_back(const char& ch)
	{
		m_pHash1->push_back(ch);
		m_pHash2->push_back(ch);
	}
	inline void push_front(const char& ch)
	{
		m_pHash1->push_front(ch);
		m_pHash2->push_front(ch);
	}
	long long Hash()const
	{
		return (long long)MOD2 * m_pHash1->m_iHash.ToInt() + m_pHash2->m_iHash.ToInt();
	}
	bool operator==(const C2DynaHashStr<MOD2>& other)  const
	{
		return (m_pHash1->m_iHash.ToInt() == other.m_pHash1->m_iHash.ToInt()) && (m_pHash2->m_iHash.ToInt() == other.m_pHash2->m_iHash.ToInt());
	}
	CDynaHashStr<>* m_pHash1;
	CDynaHashStr<MOD2>* m_pHash2;
};


//马拉车计算回文回文
class CPalindrome
{
public:
	void  CalCenterHalfLen(const string& s)
	{
		vector<char> v = { '*' };
		for (const auto& ch : s)
		{
			v.emplace_back(ch);
			v.emplace_back('*');
		}

		const int len = v.size();
		vector<int> vHalfLen(len);
		int center = -1, r = -1;
		//center是对称中心,r是其右边界（闭）
		for (int i = 0; i < len; i++)
		{
			int tmp = 1;
			if (i <= r)
			{
				int pre = center - (i - center);
				tmp = min(vHalfLen[pre], r - i + 1);
			}
			for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);
			vHalfLen[i] = --tmp;
			const int iNewR = i + tmp - 1;
			if (iNewR > r)
			{
				r = iNewR;
				center = i;
			}
		}

		m_vOddCenterHalfLen.resize(s.length());
		m_vEvenCenterHalfLen.resize(s.length());
		for (int i = 1; i < len; i++)
		{
			const int center = (i - 1) / 2;
			const int iHalfLen = vHalfLen[i] / 2;
			if (i & 1)
			{//原字符串奇数长度
				m_vOddCenterHalfLen[center] = iHalfLen;
			}
			else
			{
				m_vEvenCenterHalfLen[center] = iHalfLen;
			}
		}
	}
	/// <summary>
	/// 获取所有回文子串，左闭右开空间
	/// </summary>
	/// <param name="s">ret[i]升序。ret[i]如果包括j，则s[i...j-1]是回文</param>
	/// <returns></returns>
	vector<vector<int>> CalLeftRightExinc(const string& s)
	{
		vector<vector<int>> ret(s.length());
		CalCenterHalfLen(s);
		for (int i = 0; i < m_vOddCenterHalfLen.size(); i++) {
			{
				const int& lenMax = m_vOddCenterHalfLen[i];
				for (int len = 1; len <= lenMax; len++) {
					ret[i - len + 1].emplace_back(i + len);
				}
			}
			{//不能循环两次，否则结果不一定升序
				const int& lenMax = m_vEvenCenterHalfLen[i];
				for (int len = 1; len <= lenMax; len++) {
					ret[i - len + 1].emplace_back(i + 1 + len);
				}
			}
		}
		return ret;
	}
	vector<int> m_vOddCenterHalfLen, m_vEvenCenterHalfLen;//vOddHalfLen[i]表示 以s[i]为中心，且长度为奇数的最长回文的半长，包括s[i]
	//比如："aba" vOddHalfLen[1]为2 "abba" vEvenHalfLen[1]为2
};

//使用实例
//vector<int> vOddHalfLen, vEvenHalfLen;
//CPalindrome::Do(vOddHalfLen, vEvenHalfLen, s);

class KMP
{
public:
	virtual int Find(const string& s, const string& t)
	{
		CalLen(t);	
		for (int i1 = 0, j = 0; i1 < s.length(); )
		{
			for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
			//i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
			//t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
			if (0 == j)
			{
				i1++;
				continue;
			}
			const int i2 = i1 + j;
			j = m_vLen[j - 1];
			i1 = i2 - j;//i2不变
		}
		return -1;
	}
	//vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 部分m_vSameLen[i]会缺失
	//static vector<int> Next(const string& s)
	//{// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j]
	//	const int len = s.length();
	//	vector<int> vNext(len, -1);
	//	for (int i = 1; i < len; i++)
	//	{
	//		int next = vNext[i - 1];
	//		while ((-1 != next) && (s[next + 1] != s[i]))
	//		{
	//			next = vNext[next];
	//		}
	//		vNext[i] = next + (s[next + 1] == s[i]);
	//	}
	//	return vNext;
	//}

	const vector<int> CalLen(const string& str)
	{
		m_vLen.resize(str.length());
		for (int i = 1; i < str.length(); i++)
		{
			int next = m_vLen[i - 1];
			while (str[next] != str[i])
			{
				if (0 == next)
				{
					break;
				}
				next = m_vLen[next-1];
			}
			m_vLen[i] = next + (str[next] == str[i]);
		}
		return m_vLen;
	}
	static const vector<int> Prefix‌LongestCommonPrefix‌(const string& str)
	{
		const int N = str.length();
		vector<int> vLCP(N + 1, 0);//vPPC[i]，表示str长度为i的前缀str[0...i-1]的最长公共前后缀长度		
		for (int i = 1; i < str.length(); i++)
		{
			int preLen = vLCP[i];
			while (str[preLen] != str[i])
			{
				if (0 == preLen)
				{
					break;
				}
				preLen = vLCP[preLen];
			}
			vLCP[i+1] = preLen + (str[preLen] == str[i]);
		}
		return vLCP;
	}
protected:
	int m_c;
	vector<int> m_vLen;//m_vLen[i] 表示str[0,i]的最长公共前后缀的长度
};
class KMPEx
{
public:
	template<class T>
	static vector<int> ZFunction(const T* p, int n) {
		vector<int> z(n);
		z[0] = n;
		for (int i = 1, left = 0, r = 0; i < n; ++i) {
			if (i <= r) {//如果此if,r-i+1可能为负数
				z[i] = min(z[i - left], r - i + 1);
			}
			while ((i + z[i] < n) && (p[z[i]] == p[i + z[i]])) {
				z[i]++;
			}
			if (i + z[i] - 1 > r) left = i, r = i + z[i] - 1;
		}
		return z;//z[i] 表示S与其后缀S[i,n]的最长公共前缀(LCP)的长度
	}
	static vector<int> ZFunction(string s) {
		return ZFunction(s.c_str(), s.length());
	}
	static int MinCyc(const string& str, int unit = 1) {
		const int N = str.length();
		auto z = ZFunction(str);
		for (int k = unit; k < N; k += unit) {
			if (z[k] >= N - k) { return k; }
		}
		return N;
	}

};
//LCS(Longest Common Subsequence) 最长公共子序列
class CLCS
{
public:
	CLCS(const string& str1,const string& str2)
	{
		m_dp.assign(str1.length() + 1, vector<int>(str2.length() + 1));
		for (int i = 1; i <= str1.length(); i++)
		{
			for (int j = 1; j <= str2.length(); j++)
			{
				m_dp[i][j] = max(m_dp[i - 1][j], m_dp[i][j - 1]);
				if (str1[i - 1] == str2[j - 1])
				{
					m_dp[i][j] = max(m_dp[i][j], m_dp[i - 1][j - 1] + 1);
				}
			}
		}
	}
	vector<vector<int>> m_dp;
};

//最长公共前缀(Longest Common Prefix)
class CLCP
{
public:
	CLCP(const string& str1, const string& str2)
	{
		m_dp.assign(str1.length() , vector<int>(str2.length()));
		//str1[j...)和str2[k...]比较时, j和k不断自增，总有一个先到达末端
		for (int i = 0; i < str1.length(); i++)
		{//枚举str2 先到末端 str1[i]和str2.back对应
			m_dp[i][str2.length() - 1] = (str1[i] == str2.back());
			for (int j = i-1 ; j >= 0 ; j-- )
			{
				const int k = str2.length() - 1 - (i-j);
				if (k < 0)
				{
					break;
				}
				if (str1[j] == str2[k])
				{
					m_dp[j][k] = 1 + m_dp[j + 1][k + 1];
				}
			}			
		}
		for (int i = 0; i < str2.length(); i++)
		{//枚举str1 先到末端 str2[i]和str1.back对应
			m_dp[str1.length()-1][i] = (str1.back() == str2[i]);
			for (int j = i - 1; j >= 0; j--)
			{
				const int k = str1.length() - 1 - (i-j);
				if (k < 0)
				{
					break;
				}
				if (str1[k] == str2[j])
				{
					m_dp[k][j] = 1 + m_dp[k + 1][j + 1];
				}
			}
		}
	}
	vector<vector<int>> m_dp;
};

class CSuffArr {
public:
	CSuffArr(const string& str) :N(str.length()), m_str(str) {
		const int M = max(N, 26) + 1;
		vector<vector<pair<int, int>>> bucket(M);
		for (int i = 0; i < N; i++) {
			bucket[str[i] - 'a' + 1].emplace_back(i, 1);
		}
		BucketToRes(bucket);
		for (int len = 1; len < N; len *= 2) {
			bucket.assign(M, vector<pair<int, int>>());
			for (int i = N - len; i < N; i++) {//长度小于等于len
				bucket[m_rank[i]].emplace_back(i, 0);
			}
			for (const auto& i : m_sa) {
				if (i >= len) {
					const int iPre = i - len;
					bucket[m_rank[iPre]].emplace_back(iPre, m_rank[i]);
				}
			}
			BucketToRes(bucket);
		}
	}
	vector<int> GetH() {
		vector<int> h(N);
		for (int i = 0; i < N; i++) {
			const int iPre = (0 == i) ? 0 : h[i - 1];
			if (1 == m_rank[i]) { continue; }
			const int j = m_sa[m_rank[i] - 1 - 1];
			int cur = max(0, iPre - 1);
			for (; (i + cur < N) && (j + cur < N) && (m_str[i + cur] == m_str[j + cur]); cur++);
			h[i] = cur;
		}
		return h;
	}
	vector<int> m_rank, m_sa;
protected:
	void BucketToRes(const vector<vector<pair<int, int>>>& bucket) {
		m_sa.clear();
		m_rank.resize(N);
		int rank = 0;
		for (auto& v : bucket) {
			for (int i = 0; i < v.size(); i++) {
				if ((0 == i) || (v[i].second != v[i - 1].second)) { rank++; }
				m_sa.emplace_back(v[i].first);
				m_rank[v[i].first] = rank;
			}
		}
	}
	string m_str;
	const int N;
};

class CBracket
{
public:
	static int ToInt(const char& ch)
	{
		if ('(' == ch)
		{
			return 1;
		}
		return (')' == ch) ? -1 : 0;
	}
	static bool IsVilid(const string& str)
	{
		int num = 0;
		for (const auto& ch : str)
		{
			num += ToInt(ch);
			if (num < 0)
			{
				return false;
			}
		}
		return 0 == num;
	}
};